package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author feizns
 * @since 2020/1/7
 */
public class ZigzagLevelOrder {

    public static void main(String[] args) {

    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        return levelsOrder(queue, 0, new LinkedList<>());
    }

    private static List<List<Integer>> levelsOrder(Queue<TreeNode> queue, int level, List<List<Integer>> lists) {
        Queue<TreeNode> newQueue = new LinkedList<>();
        List<Integer> tmp = new LinkedList<>();
        while ( !queue.isEmpty() ) {
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if ( node.left != null )
                newQueue.add(node.left);
            if ( node.right != null )
                newQueue.add(node.right);
        }
        if ( level != 0 && level % 2 == 0 )
            Collections.reverse(tmp);
        lists.add(tmp);
        if ( !newQueue.isEmpty() )
            levelsOrder(newQueue, level + 1, lists);
        return lists;
    }

}
